package com.future;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Description:
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 4, k = 2
 * 输出：
 * [
 * [2,4],
 * [3,4],
 * [2,3],
 * [1,2],
 * [1,3],
 * [1,4],
 * ]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combinations
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/2/22 23:13
 */
public class Solution_77 {

    public static void main(String[] args) {
        int n = 4;
        int k = 2;
        System.out.println("start:" + System.currentTimeMillis());
        List<List<Integer>> combine = combine(n, k);
        System.out.println("end:" + System.currentTimeMillis());
        System.out.println(Arrays.asList(combine));
    }


    public static List<List<Integer>> combine(int n, int k) {
        PermuteObj obj = new PermuteObj(n, k);
        List<List<Integer>> an = obj.getAns();
        Set<List<Integer>> set = new HashSet<>(an);
        return set.stream().collect(Collectors.toList());
    }


    static class PermuteObj {

        List<List<Integer>> ans = new ArrayList<>();

        int length;
        int n;

        public PermuteObj(int n, int k) {
            this.n = n;
            length = k;
            if (n == 0) {
                return;
            }
            process(new ArrayDeque<>(), 1);
        }

        public List<List<Integer>> getAns() {
            return ans;
        }

        private void process(Deque<Integer> paths, int curIndex) {
            if (paths.size() == length) {
                ArrayList<Integer> integers = new ArrayList<>(paths);
                ans.add(integers);
                return;
            }
            for (int i = curIndex; i <= n; i++) {
                paths.addLast(i);
                process(paths, i + 1);
                paths.removeLast();
            }
        }
    }

}
